package com.ting.test.algorithms.堆;

/**
 * 给定很多线段，每个线段都有两个数[start, end]，
 * 表示线段开始位置和结束位置，左右都是闭区间
 * 规定：
 * 1）线段的开始和结束位置一定都是整数值
 * 2）线段重合区域的长度必须>=1
 * 返回线段最多重合区域中，包含了几条线段
 * <p>
 * 思路:
 * 先找出所有线段中出现过的最小的开始位置min和最大的结束位置max
 * 以min+0.5为起点，max-0.5为终点，1为步长
 * 遍历每个点在所有线段中出现的次数，其中最大的那个就是结果
 * 比如{{1, 3}, {1, 6}, {2, 4}};
 * min=1,max=6
 * 那么
 * 1.5出现了2次
 * 2.5出现了3次
 * 3.5出现了2次
 * 4.5出现了2次
 * 5.5出现了1次
 * 因此 1.5的出现次数最多，对应的重合区域为[1,2]
 */
public class 最大线段重合问题 {
    public static void main(String[] args) {
        int arr[][] = new int[][]{{1, 3}, {1, 6}, {2, 4}};
        int result = func(arr);
        System.out.println(result);
    }

    private static int func(int[][] arr) {
        if (arr == null) {
            return 0;
        }

        int max = arr[0][0], min = arr[0][1];
        for (int[] temp : arr) {
            if (temp[0] < min) {
                min = temp[0];
            }
            if (temp[1] > max) {
                max = temp[1];
            }
        }
        System.out.println("min=" + min + ",max=" + max);
        int maxCount = 0;
        for (double i = min + 0.5; i < max; i++) {
            int count = 0;
            for (int[] temp : arr) {
                if (temp[0] < i && temp[1] > i) {
                    count++;
                }
            }
            if (maxCount < count) {
                maxCount = count;
            }
        }
        return maxCount;
    }


}
